/*
 * Copyright 2008 Max Kugland
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.splink.library.tree {
	import org.splink.library.IFinalizable;
	import org.splink.library.utils.ArrayUtils;

	import flash.xml.XMLDocument;
	import flash.xml.XMLNode;

	/**
	 * A tree of nodes. The <code>Tree</code> contains a root <code>INode</code> which
	 * is the root of a tree of nodes. So the root node may contain other nodes which may
	 * contain more nodes and so on.
	 * 
	 * There are also static methods to manipulate, serialize or extract information from 
	 * the tree.
	 * 
	 * @see org.splink.library.tree.INode
	 * @author Max Kugland
	 */
	public class Tree implements IFinalizable {
		private var _root : INode;

		/**
		 * @param root the root node of the tree
		 */
		public function Tree(root : INode = null) {
			_root = root;
		}

		/**
		 * Return the root <code>Node</code> of the tree.
		 * 
		 * @return the root <code>Node</code>.
		 */
		public function get root() : INode {
			return _root;
		}

		/**
		 * Set the root <code>Node</code> for the tree.
		 * 
		 * @param rootNode the root <code>Node</code> to set.
		 */
		public function set root(root : INode) : void {
			_root = root;
			_root.parent = null;
		}

		/**
		 * Returns the <code>Tree</code> as an Array of <code>Node</code> objects. The nodes in the
		 * Array are generated from a pre-order traversal of the tree.
		 * 
		 * @return an Array of <code>Node</code> objects
		 */
		public function toArray() : Array {
			var ar : Array = new Array();
			walk(_root, ar);
			return ar;
		}

		/**
		 * Walks recursively through the Tree and adds all <code>Node</code> instances within
		 * the tree to the given array.
		 * 
		 * @param node the starting <code>Node</code>.
		 * @param ar the output of the walk.
		 */
		private function walk(node : INode, ar : Array) : void {
			ar.push(node);
			for each (var n : INode in node.children) {
				walk(n, ar);
			}
		}

		/**
		 * Finalizes the complete tree, beginning with it's root <code>Node</code>
		 * 
		 * @inheritDoc
		 */
		public function finalize() : void {
			_root.finalize();
		}

		/**
		 * Visits all nodes beneath the given node and invokes the given function with each
		 * of the nodes as argument.
		 * 
		 * @param node the <code>Nodes</code> whose sub nodes are visited
		 * @param fnc a function with one parameter typed as <code>Node</code> 
		 */
		public static function visit(node : INode, fnc : Function) : void {
			for each (var n : INode in node.children) {
				fnc(n);
				visit(n, fnc);
			}
		}

		/**
		 * Clones a <code>Node</code>. <code>clone</code> recursively walks trough the node tree 
		 * from the given node, clones each node in the tree and returns the clone
		 * of the given node. The data of the nodes is not cloned.
		 * 
		 * @param node the node to clone (it's children and theit children and so on are cloned, too)
		 * @return the cloned node
		 */
		public static function clone(node : INode) : INode {
			var r : INode = new Node(node.id, node.data);
			cloneHelper(node, r);
			return r;
		}

		private static function cloneHelper(node : INode, newNode : INode) : void {
			for each (var n : INode in node.children) {
				cloneHelper(n, newNode.add(new Node(n.id, n.data)));
			}
		}

		/**
		 * Serializes the <code>Tree</code> into an xml object
		 * 
		 * @param tree the tree to be serialized
		 * @param rootNodeName the name used for the root node
		 * @param nodeName the name of all nodes exept the root node, if the value is null, the node's
		 * id is used as its name instead
		 */
		public static function toXml(tree : Tree, rootNodeName : String = "tree", nodeName : String = "node") : XML {
			var x : XMLDocument = new XMLDocument();
			var xmlNode : XMLNode = x.createElement(rootNodeName);
			x.appendChild(xmlNode);
			
			getXml(tree.root, xmlNode, x, nodeName);
			return new XML(x.toString());
		}

		/**
		 * Recursively serializes the <code>Tree</code> into xml
		 * 
		 * @param node the current <code>Node</code>
		 * @param xml the current XMLNode
		 * @param xml the XMLDocument which is used to create elements
		 */
		private static function getXml(node : INode, xml : XMLNode, x : XMLDocument, nodeName : String) : void {
			for each (var n : INode in node.children) {
				if(nodeName == null) nodeName = n.id;
				
				var e : XMLNode = x.createElement(nodeName);
				if(nodeName != n.id) e.attributes = {id:n.id}; else nodeName = null;
				xml.appendChild(e);
				getXml(n, e, x, nodeName);
			}
		}

		/**
		 * Builds the <code>Tree</code> from an XML object. XML that can be serialized into a
		 * <code>Tree</code> must use the following format: 
		 * <tree><node id="node1"><node id="node2"/></node></tree>
		 * 
		 * @param xml the xml which is to be transformed into the <code>Tree</code>
		 * @param clazz the Class which is to be used as class for the <code>Tree</code>'s 
		 * <code>Node</code>s. The passed clazz must be a subclass of the <code>Node</code>
		 * class. The default class is the <code>Node</code> class
		 */
		public static function fromXml(tree : Tree, xml : XML, clazz : Class = null) : Tree {
			if(clazz == null) clazz = Node;
			var x : XMLDocument = new XMLDocument();
			x.parseXML(xml);
			
			createTree(x.firstChild, tree.root = new clazz("tree", null), clazz);
			return tree;
		}

		private static function createTree(xmlNode : XMLNode, node : INode, clazz : Class) : void {
			for each(var c : XMLNode in xmlNode.childNodes) {
				if(c.nodeName != null) {
					var n : INode = new clazz(c.attributes["id"], node);
					node.add(n);
					createTree(c, n, clazz);
				}
			}
		}

		/**
		 * Recursively collects all parent nodes of the given node until the rootnode is reached
		 * 
		 * @param node the node from which to start
		 * @return an array which contains all parent nodes of the given node
		 */
		public static function getParentNodeChain(node : INode) : Array {
			var chain : Array = new Array();
			getParentNodeChainHelper(node, chain);
			return chain;
		}

		private static function getParentNodeChainHelper(node : INode, chain : Array) : void {
			var parent : INode = node.parent as INode;
			if(parent) {
				chain.push(parent);
				getParentNodeChainHelper(parent, chain);
			}
		}

		/**
		 * Checks the parent node chain of both given nodes for a common parent 
		 * and returns it
		 * 
		 * @param node1
		 * @param node2
		 * @return the first common parent node of the given nodes
		 */
		public static function getCommonParent(node1 : INode, node2 : INode) : INode {
			var chain1 : Array = getParentNodeChain(node1);
			var chain2 : Array = getParentNodeChain(node2);
			
			for each (var n1 : INode in chain1) {
				for each (var n2 : INode in chain2) {
					if(n1 == n2) {
						return n1;
					}
				}	
			}
			return null;
		}

		/**
		 * Fills the nodes array recursively with all parent nodes of the given node until
		 * the given chain array contains one of the parents of the given node.
		 * 
		 * @param node the node from which to start the recursion down the tree
		 * @param chain the array which defines all nodes at which to stop the recursion 
		 * @return an array containing the parent nodes of the given node
		 */
		public static function getNodesUntilCommonParent(node : INode, chain : Array) : Array {
			var nodes : Array = new Array();
			getNodesUntilCommonParentHelper(node, nodes, chain);
			return nodes;
		}

		private static function getNodesUntilCommonParentHelper(node : INode, nodes : Array, chain : Array) : void {
			nodes.push(node);
			var parent : INode = node.parent as INode;
			if(parent && (!ArrayUtils.contains(chain, parent) && !ArrayUtils.contains(chain, node))) {
				getNodesUntilCommonParentHelper(parent, nodes, chain);
			}
		}

		/**
		 * Recursively seeks the node with the given id within the <code>Tree</code> If no matching 
		 * <code>INode</code> can be found null is returned
		 * 
		 * @param id the id of the <code>INode</code> to find
		 * @param node the <code>INode</code> from which to start the search
		 * @return the found <code>INode</code>
		 */
		public static function getNodeById(id : String, node : INode) : INode {
			if(node.id == id) {
				return node;
			}
			
			for each (var n : INode in node.children) {
				var r : INode = getNodeById(id, n);
				if(r != null) return r;
			}
			
			return null;
		}

		/**
		 * Finds and returns the previous leaf node from the given <code>INode</code>.
		 * The search algorithm will move up the tree hierarchy and inspect all 
		 * parents of the <code>INode</code>. If a branch can be found wich is 
		 * more left than the branch of the given <code>INode</code> then the 
		 * last leaf of this branch will be returned. 
		 * 
		 * @param node The <code>INode</code> where the search should start.
		 * @return The previous leaf node. <code>null</code> if the given <code>INode</code> has no previous leaf node.
		 */
		public static function getPreviousLeaf(node : INode) : INode {
			while(node.parent != null) {
				var childIndex : int = node.parent.children.indexOf(node);
				if(childIndex > 0) {
					return getLastLeaf(node.parent.children[childIndex - 1]);					  
				}
				else node = node.parent;
			}
			return null;
		}
		
		/**
		 * Finds and returns the next leaf node from the given <code>INode</code>.
		 * The search algorithm will move up the tree hierarchy and inspect all 
		 * parents of the <code>INode</code>. If a branch can be found wich is 
		 * more right than the branch of the given <code>INode</code> then the 
		 * first leaf of this branch will be returned. 
		 * 
		 * @param node The <code>INode</code> where the search should start.
		 * @return The next leaf node. <code>null</code> if the given <code>INode</code> has no next leaf node.
		 */
		public static function getNextLeaf(node : INode) : INode {
			while(node.parent != null) {
				var childIndex : int = node.parent.children.indexOf(node);
				if(childIndex < node.parent.children.length - 1) {
					return getFirstLeaf(node.parent.children[childIndex + 1]);					  
				}
				else node = node.parent;
			}
			return null;
		}
		
		/**
		 * Finds and returns the first leaf that is a descendant of the given <code>INode</code> - either the <code>INode</code> itself 
		 * or its first child's first leaf. Returns the given <code>INode</code> if it is a leaf.
		 * 
		 * @param node The <code>INode</code> that acts as the root node for the search.
		 * @return the first leaf in the subtree rooted at the given node
		 */
		public static function getFirstLeaf(node : INode) : INode {			
			while(node.isLeaf == false) {
				node = node.children[0];
			}			
			return node;			
		}
		
		/**
		 * Finds and returns the last leaf that is a descendant of the given <code>INode</code> - either the <code>INode</code> itself 
		 * or its last child's last leaf. Returns the given <code>INode</code> if it is a leaf.
		 * 
		 * @param node The <code>INode</code> that acts as the root node for the search.
		 * @return the last leaf in the subtree rooted at the given node
		 */
		public static function getLastLeaf(node : INode) : INode {
			while(node.isLeaf == false) {
				node = node.children[node.children.length - 1];
			}
			return node;
		}

		/**
		 * Recursively collects children of the given node.
		 * 
		 * @param node the node whiches children to return
		 * @return all children of the given node
		 */
		public static function getAllChildren(node : INode) : Array {
			var childs : Array = new Array();
			getAllChildrenHelper(node, childs);
			return childs;
		}

		private static function getAllChildrenHelper(node : INode, childs : Array) : void {
			for each (var n : INode in node.children) {
				childs.push(n);
				getAllChildrenHelper(n, childs);
			}
		}
		
		/** 
		 * Returns the longest distance from a node to a leaf.
		 * 
		 * @param node the node that acts as the tree root
		 * @return the longest distance from the node to a leaf 
		 */
		public static function getDepth(node : INode) : int {
			var layer : int = node.layer;
			visit(node, function(n : INode) : void {
				if(n.layer > layer) {
					layer = n.layer;
				}
			});
			return layer - node.layer;
		}
		
		/** 
		 * Returns a preorder node index that can be used to compare node positions 
		 * in a tree. To calculate the index any node will be counted first and then
		 * all of its children.
		 * 
		 * @param root The root node where the index calculation should start
		 * @param node The node to search for 
		 * @return The index of the node in the tree. Returns -1 if the node is not a descendant of root. 
		 */
		public static function getNodeIndex(root : INode, node : INode) : int {
			return getPreOrderNodes(root).indexOf(node);
		}
		
		/**
		 * Returns a preorder list of the given root node and all of its subnodes.
		 * Preorder means that the parent note itself is included in the node list 
		 * before all of its children.
		 * 
		 * @param root The root node of the tree.
		 * @return A preorder list of the root node and all its descendants.
		 */
		public static function getPreOrderNodes(root : INode) : Array {			
			var nodes : Array = new Array();
			getPreOrderSubNodes(root, nodes);
			return nodes;
		}
		
		/**
		 * Helper method for recursive calls to get a preorder list of tree nodes.
		 * 
		 * @param node The root node of the list.
		 * @param nodes An array where the root node and all of its descendants should be added to.
		 */
		private static function getPreOrderSubNodes(node : INode, nodes : Array) : void{
			nodes.push(node);
			for each(var child : INode in node.children) {
				getPreOrderSubNodes(child, nodes);
			}
		}		
	}
}